/**
 * @param {number[]} nums
 * @return {number[]}
 */

var sortArray = function (nums) {
  const N = nums.length;
  quickSort(nums, 0, N - 1);
  return nums;
};

function quickSort(nums, left, right) {
  if (right <= left) {
    return;
  }
  let pIndex = partition(nums, left, right);
  quickSort(nums, left, pIndex - 1);
  quickSort(nums, pIndex + 1, right);
}

function partition(nums, left, right) {

  let pivot = nums[left];
  // 为两个数组分别定义一个指针
  let i = left + 1;
  let j = right;

  while (true) {
    while (i <= right && nums[i] <= pivot) {
      i++;
    }
    while (j > left && nums[j] > pivot) {
      j--;
    }
    if (i >= j) {
      break;
    }
    swap(nums, i, j);
    i++;
    j--;
  }
  swap(nums, left, j);
  return j;
}

function swap(nums, i, j) {
  let temp = nums[i];
  nums[i] = nums[j];
  nums[j] = temp;
}

let arr = sortArray([3, 4, 2, 1,4,6,3,8,9]);
console.log(arr);
